﻿namespace array_demo.Model.Tree
{
    /// <summary>
    /// 左倾红黑树 为了不退化一个链表 红链接均为左链接，（连续数据添加）
    /// 没有任何一个节点同时和两条红链接相连
    /// 红节点均为左节点
    /// 树是完美的黑平衡，即空节点到根节点路径经过黑色节点的数量是相同的
    /// 新加入的节点均为红节点
    /// 根节点是黑色的
    /// </summary>
    public class RbTree<E> where E : IComparable
    {
        private const bool Red = true;

        private const bool Black = true;

        private class Node
        {
            public E e;
            public Node left;
            public Node right;
            public bool color;

            public Node(E e)
            {
                this.e = e;
                this.left = null;
                this.right = null;
                color = Red;
            }
        }

        /// <summary>
        /// 根节点
        /// </summary>
        private Node root;

        /// <summary>
        /// 数据长度
        /// </summary>
        private int N;

        public RbTree()
        {
            root = null;
            N = 0;
        }

        public int Count { get { return N; } }

        public bool IsEmpty { get { return N == 0; } }


        /// <summary>
        /// 如果出现右节点为红色而左节点是黑色，需要进行左旋转操作
        /// 左旋转，将红色右节点转换为左节点
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private bool IsRed(Node node)
        {
            if (node == null)
                return Black;
            return node.color;
        }

        //    node                      x
        //    /  \       左旋转        /   \
        //   T1   x     ------->     node  T3      
        //       / \                 /  \
        //      T2 T3               T1  T2
        private Node LeftRotate(Node node)
        {
            Node x = node.right;
            node.right = x.left;
            x.left = node;
            x.color = node.color;
            node.color = Red;
            return x;
        }

        // 如果左右节点均为红色，进行颜色翻转
        private void FlipColor(Node node)
        {
            node.color = Red;
            node.left.color = Black;
            node.right.color = Black;
        }

        //如果出现连续两个红色的左节点，进行右旋转
        //    node                      x
        //    /  \       右旋转        /   \
        //   x    T2 ------->        T3   node        
        //  / \                           /  \
        // T3 T1                          T1  T2

        private Node RightRotate(Node node)
        {
            Node x = node.left;
            //变化了的先赋值
            node.left = x.right;
            x.right = node;
            x.color = node.color;
            node.color = Red;
            return x;
        }


        /// <summary>
        /// 往红黑树添加元素
        /// </summary>
        /// <param name="e"></param>

        public void AddV1(E e)
        {
            root = Add(root, e);
            root.color = Black;
        }

        private Node Add(Node node, E e)
        {
            // 判断根节点为不为空
            if (node == null)
            {
                N++;
                return new Node(e);// 默认为红节点
            }

            // 判断插入的值和节点是否小于
            if (e.CompareTo(node.e) < 0)
            {
                node.left = Add(node.left, e);
            }
            else if (e.CompareTo(node.e) > 0)
            {
                node.right = Add(node.right, e);
            }

            //三种情况
            // 如果右节点是红色，左节点是黑色就需要进行左旋转
            if (IsRed(node.right) && !IsRed(node.left))
            {
                node = LeftRotate(node);
            }

            // 如果出现连续两个红色的左节点，进行右旋转
            if (IsRed(node.left) && IsRed(node.left.left))
            {
                node = RightRotate(node);
            }

            //如果左右节点均为红色，进行颜色翻转
            if (IsRed(node.right) && IsRed(node.left))
            {
                FlipColor(node);
            }
            return node;
        }

        public bool Contains(E e)
        {
            return Contains(root, e);
        }

        private bool Contains(Node node, E e)
        {
            if (node == null)
                return false;

            if (e.CompareTo(node.e) == 0)
                return true;

            else if (e.CompareTo(node.e) < 0)
                return Contains(node.left, e);
            else
                return Contains(node.right, e);
        }

        public int MaxHeight()
        {
            return MaxHeight(root);
        }

        private int MaxHeight(Node node)
        {
            if (node == null) return 0;
            // +1 node 本身节点高度
            return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
        }
    }
}
